package com.ruijixiang.leetcode.weekly.leetcode2024.leetcode20241006;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class leetcode3311 {

    public int[][] constructGridLayout(int n,int[][] edges){
        List<Integer>[] g=new ArrayList[n];
        Arrays.setAll(g,i->new ArrayList<>());
        for(int[] e : edges){
            int x=e[0];
            int y=e[1];
            g[e[0]].add(e[1]);
            g[e[1]].add(e[0]);
        }

        // 每种度数选一个点
        int[] degToNode=new int[5];
        Arrays.fill(degToNode,-1);
        for(int x=0;x<n;x++){
            degToNode[g[x].size()]=x;
        }

        List<Integer> row=new ArrayList<>();
        if(degToNode[1]!=-1){
            // 答案只有一列
            row.add(degToNode[1]);
        }else if(degToNode[4]==-1){
            // 答案只有两列
            int x=degToNode[2];
            for(int y : g[x]){
                if(g[y].size()==2){
                    row.add(x);
                    row.add(y);
                    break;
                }
            }
        }else{
            // 答案至少三列
            // 寻找度数为23333....32的序列作为第一排
            int x=degToNode[2];
            row.add(x);
            int pre=x;
            x=g[x].get(0);
            while(g[x].size()==3){
                row.add(x);
                for(int y : g[x]){
                    if(y!=pre && g[y].size()<4){
                        pre=x;
                        x=y;
                        break;
                    }
                }
            }
            row.add(x);// x的度数为2
        }

        int k=row.size();
        int[][] ans=new int[n/k][k];
        boolean[] vis=new boolean[n];
        for(int j=0;j<k;j++){
            int x=row.get(j);
            ans[0][j]=x;
            vis[x]=true;
        }

        for(int i=0;i<ans.length;i++){
            for(int j=0;j<k;j++){
                for(int y : g[ans[i-1][j]]){
                    // 上左右的邻居都访问过了，没有访问过的邻居只会在下面
                    if(!vis[y]){
                        vis[y]=true;
                        ans[i][j]=y;
                        break;
                    }
                }
            }
        }
        return ans;
    }
}
